/**
 * 
 */
package leetCode;

/**
 * @author zhongfang
 *
 */
public class ValidateBinarySearchTree {
	  public class TreeNode {
		      int val;
		      TreeNode left;
		      TreeNode right;
		      TreeNode(int x) { val = x; }
		  }
    public boolean isValidBST(TreeNode root) {
        if(root==null){
            return true;
        }
        int[] a=new int[2];
        return isValidBSThelper(root,a);
    }
    
    public boolean isValidBSThelper(TreeNode root,int[] a){
        if(root.left!=null){
            int[] left=new int[2];
            if(!isValidBSThelper(root.left,left)){
                return false;
            }
            if(left[1]>=root.val){
                return false;
            }
            a[0]=left[0];
        }
        
        if(root.right!=null){
            int[] right=new int[2];
            if(!isValidBSThelper(root.right,right)){
                return false;
            }
            if(right[0]<=root.val){
                return false;
            }
            a[1]=right[1];//max=max of right subtree
        }
        return true;
    }
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
	}

}
